/**
 * 动态规划思想:
 *
 * 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。
 * 请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？
 *
 * Date: 2022-09-30
 * Time: 15:00
 */
public class algorithm {

    public static int rectCover(int target) {
        // f(n): n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形的方法数
        // f(n) = f(n-1)[最后一个竖着放] + f(n-2)[最后一个横着放].
        // f(1) = 1   f(2) = 2   f(3) = 3
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target];
        // 此处动态规划并不是最优的, 只是用来理解这种思想而已.
    }

    public static void main(String[] args) {
        int k = 10;
        System.out.println(rectCover(k));
    }
}
